426. Convert Binary Search Tree to Sorted Doubly Linked List
Medium

Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.

You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.

 

Example 1:

Input: root = [4,2,5,1,3]


Output: [1,2,3,4,5]

Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

Example 2:

Input: root = [2,1,3]
Output: [1,2,3]

Example 3:

Input: root = []
Output: []
Explanation: Input is an empty tree. Output is also an empty Linked List.

Example 4:

Input: root = [1]
Output: [1]

 

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000
  • All the values of the tree are unique.
Accepted
125,100
Submissions
201,789
Seen this question in a real interview before?
Companies
Similar Questions

Average Rating: 4.59 (71 votes)

Premium

Solution


How to traverse the tree

There are two general strategies to traverse a tree:

  • Depth First Search (DFS)

    In this strategy, we adopt the depth as the priority, so that one would start from a root and reach all the way down to certain leaf, and then back to root to reach another branch.

    The DFS strategy can further be distinguished as preorder, inorder, and postorder depending on the relative order among the root node, left node and right node.

  • Breadth First Search (BFS)

    We scan through the tree level by level, following the order of height, from top to bottom. The nodes on higher level would be visited before the ones with lower levels.

On the following figure the nodes are numerated in the order you visit them, please follow 1-2-3-4-5 to compare different strategies.

postorder

Here the problem is to implement DFS inorder traversal in a textbook recursion way because of in-place requirement.


Approach 1: Recursion

Algorithm

Standard inorder recursion follows left -> node -> right order, where left and right parts are the recursion calls and node part is where all processing is done.

Processing here is basically to link the previous node with the current one, and because of that one has to track the last node which is the largest node in a new doubly linked list so far.

postorder

One more detail : one has to keep the first, or the smallest, node as well to close the ring of doubly linked list.

Here is the algorithm :

  • Initiate the first and the last nodes as nulls.

  • Call the standard inorder recursion helper(root) :

    • If node is not null :

      • Call the recursion for the left subtree helper(node.left).

      • If the last node is not null, link the last and the current node nodes.

      • Else initiate the first node.

      • Mark the current node as the last one : last = node.

      • Call the recursion for the right subtree helper(node.right).

  • Link the first and the last nodes to close DLL ring and then return the first node.

Implementation

Current
1 / 9

Complexity Analysis

  • Time complexity : O(N)\mathcal{O}(N) since each node is processed exactly once.

  • Space complexity : O(N)\mathcal{O}(N). We have to keep a recursion stack of the size of the tree height, which is O(logN)\mathcal{O}(\log N) for the best case of completely balanced tree and O(N)\mathcal{O}(N) for the worst case of completely unbalanced tree.

Report Article Issue

Comments: 41
StonedCoders's avatar
Read More

Java iterative solution.

 public Node treeToDoublyList(Node root) {
    if( root == null) return root;
    Node dummy = new Node(0);
    Node prev = dummy;
    Stack<Node> stack = new Stack();
    Node curr = root;

    while(!stack.isEmpty()|| curr != null){
        while(curr!= null){
        stack.push(curr);
        curr = curr.left;
        }
   
    curr = stack.pop();
    prev.right = curr;
    curr.left = prev;
    prev = curr;
    curr = curr.right;
    }
      dummy.right.left = prev;
       prev.right = dummy.right;
    return dummy.right;
}

}

53
Show 9 replies
Reply
Share
Report
tripling's avatar
Read More

For folks saying it is not in-place, if I am not wrong, academically in-place means mutating the input and not returning newly allocated data. That is you can use extra space but in the end the returned value should not be something newly created but instead all changes done in the given input only.

46
Show 2 replies
Reply
Share
Report
coder_xyzzy's avatar
Read More

This is not O(1) space. It is O(tree depth), so O(n) worst case and O(log(n)) average case.

Keep in mind that the recursive call stack takes space, and there will be (at maximum depth) one stack from for each level in the tree.

38
Show 7 replies
Reply
Share
Report
Cheney1993's avatar
Read More

Approach 1: Iteration
Python3

def treeToDoublyList(self, root: 'Node') -> 'Node':
    
    if not root:
        return None
    
    stack = [root]
    first, curr, last = None, root.left, None
    
    while curr or stack:
        if curr:
            stack.append(curr)
            curr = curr.left
            continue
        if stack:
            curr = stack.pop()
            if not first:
                first = curr
            if last:
                last.right = curr
                curr.left = last
            last = curr
            curr = curr.right
    
    first.left = last
    last.right = first
    
    return first

Time complexity : O(N)
Space complexity : O(N)

8
Show 2 replies
Reply
Share
Report
zeus1985's avatar
Read More

Another way is to do inOrder traversal and add all nodes to a arrayList. Then do linkage later.

19
Show 2 replies
Reply
Share
Report
stevenkinouye's avatar
Read More

Here is my O(1) space solution using Morris In Order Traversal
https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/discuss/534869/JavaScript-Morris-In-Order-Traversal-O(n)-Time-O(1)-Space

var treeToDoublyList = function(root) {
    if (!root) return root;
    let head = new Node();
    let last = head;
    
    let node = root;
    while (node) {
        if (node.left) {
            let predecessor = node.left;
            while (predecessor.right && predecessor.right !== node) {
                predecessor = predecessor.right;
            }
            if (predecessor.right === null) {
                predecessor.right = node;
                node = node.left;
            } else {
                last.right = node;
                node.left = last;
                last = node;
                // predecessor.right = null;  <= this is the line for normal
                node = node.right;
            }
        } else {
            last.right = node;
            node.left = last;
            last = node;
            node = node.right;
        }
    }
    last.right = head.right;
    head.right.left = last;
    return head.right;
};

5
Reply
Share
Report
s961206's avatar
Read More

Wow, amazing clean code. Respect!

10
Reply
Share
Report
himani_01's avatar
Read More

Great solution. Basically we are using inorder traversal and just following the order of its traversal to update the last node.

3
Reply
Share
Report
ntkw's avatar
Read More

Why is this related with Divide and Conquer?

3
Reply
Share
Report
soccer_player's avatar
Read More

Folks, I think "in-place" here ONLY means do not use inorder traversal first to go through all the nodes. It does not mean not use recursion or extra space. Apparently leetcode has different definitions of in-place with all the others.

6
Show 1 reply
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.